package jsc.structureDeDonnees;

import java.io.File;
import java.io.IOException;

import jsc.base.TextFileReader;


/** 
 * Une classe pour les arbres binaires de recherche de String
 * un arbre binaire de recherche est défini par le schéma d'induction :
 *     l'arbre vide est un arbre binaire de recherche
 *     si x est un String, si gauche et droite sont des arbres binaires de recherche
 *        et que x est supérieur à la racine de gauche et x est inférieur à la racine de droite
 *        alors <x, gauche, droite> est un arbre binaire de recherche.
 * @author helen
 */

public class ABRString implements StructureDico{
	private String racine; //l'élément
	private ABRString gauche;  // le sous-arbre gauche
	private ABRString droite;  // le sous-arbre droit

	/** constructeur par défaut, ABR vide
	 */
	public ABRString() {
		this(null,null,null);
	}

	/** construit un arbre de racine o, de sous-arbre gauche 
	 * et  droit nuls
	 */
	private ABRString(String o) { 
		this(o,null,null);
	}

	/** construit un arbre de racine o, de sous-arbre gauche g
	 * et de sous-arbre droit d
	 */
	private ABRString(String o, ABRString g, ABRString d) {
		racine = o;
		gauche = g;
		droite = d;
	}

	/** construit un ABR qui contient les mêmes éléments que le 
	 * tableau t
	 * @param t: un tableau de String trié par ordre croissant
	 * Appelle la méthode "toABR"
	 */
	public ABRString(String[] t) {
		this.ajouter(t);
	}

	public boolean vide() {
		return racine==null && gauche==null && droite==null;
	}

	// pour afficher l'arbre
	public String toString() {
		if (!vide()) return toStringAux();
		return "Arbre vide";
	}

	private String toStringAux() {
		String s = "\nVALEUR : " + racine + " ";
		if (gauche!=null)
			s = s + "GAUCHE : " + gauche.racine + " ";
		if (droite!=null)
			s= s + "DROITE : " + droite.racine + " ";
		if (gauche!=null) s= s + gauche.toStringAux();
		if (droite!=null) s= s + droite.toStringAux();
		return s;
	}

	///////////////////////////////////////////////////////////////
	// méthodes à compléter
	///////////////////////////////////////////////////////////////

	/* Consequent : this contient o et est un arbre de recherche
	 * complexité : theta(log(n)) dans le meilleur des cas ie si l'arbre est équilibré
	 *              theta(n) dans le pire des cas ie si l'arbre est dégénéré
	 * NB: les clefs sont uniques dans l'arbre, donc si il existe un objet 
	 * ayant la même clef que o dans l'arbre, alors o n'est pas ajouté
	 * NB : utiliser la méthode "compareTo" pour comparer les String
	 *      (voir interface Comparable)
	 */
	public void ajouter(String o) {
		if(this.vide()){
			this.racine = o;
		}else{
			int comparaison = this.racine.compareTo(o);
			if(comparaison > 0){
				if(this.gauche == null){
					this.gauche = new ABRString(o);
				}else{
					this.gauche.ajouter(o);
				}
			}else if(comparaison < 0){
				if(this.droite == null){
					this.droite = new ABRString(o);
				}else{
					this.droite.ajouter(o);
				}
			}
		}
	}

	/**
	 * ajoute les élements du tableau ordonné à l'arbre
	 * @param t
	 */
	private void ajouter(String[] t){
		int milieu = t.length/2;
		this.ajouter(t[milieu]);
		this.gauche = this.toABR(t, 0, milieu-1);
		this.droite = this.toABR(t, milieu+1, t.length-1);
	}


	/** renvoie un ABR qui contient les mêmes éléments que les 
	 * éléments d'indices i àj du tableau t 
	 * Fonctionne de façon dichotomique pour que l'ABR soit équilibré: 
	 *     on met l'élément qui est au milieu du tableau en racine de l'arbre
	 *     et on construit récursivement les arbres gauche (resp. droit) à partir
	 *     de la moitié gauche (resp. droite) du tableau.
	 */ 
	private ABRString toABR(String[] t, int i , int j) {
		if(i == j){
			return new ABRString(t[i]);
		}else if(i < j){
			int milieu = (i+j)/2;
			return new ABRString(t[milieu], this.toABR(t, i, milieu-1), this.toABR(t, milieu+1, j));
		}else{
			return null;
		}
	}


	/* Consequent : renvoie vrai si o est dans l'arbre, renvoie false sinon
	 * complexité : theta(1) dans le meilleur des cas
	 *              theta(n) dans le pire des cas
	 */
	public boolean existe(String o) {
		if(this.vide()){
			return false;
		}else{
			int comparaison = this.racine.compareTo(o);
			if (comparaison == 0){
				return true;
			}
			else if(comparaison > 0){
				if(this.gauche != null){
					return this.gauche.existe(o);
				}else{
					return false;
				}
			}else{
				if(this.droite != null){
					return this.droite.existe(o);
				}else{
					return false;
				}
			}
		}
	}

	/**
	 * renvoit le nombre d'élément de l'arbre
	 * @return
	 */
	public int size() {
		if(this.vide()){
			return 0;
		}else{
			if(this.gauche != null && this.droite != null){
				return (this.gauche.size() + this.droite.size() + 1);
			}else if(this.gauche != null){
				return this.gauche.size() + 1;
			}else if(this.droite != null){
				return this.droite.size() + 1;
			}else{
				return 1;
			}
		}
	}

	public String[] tableau(){
		int taille = this.size();
		String tableau[] = new String[taille];

		if(this.gauche != null){
			int size = this.gauche.size();
			tableau[size] = this.racine;
			this.gauche.remplir(tableau, 0, size-1);
			if(this.droite != null){
				this.droite.remplir(tableau, size+1, taille-1);
			}
		}else{
			tableau[0] = this.racine;
			if(this.droite != null){
				this.droite.remplir(tableau, 1, taille-1);
			}
		}
		return tableau;
	}

	private void remplir(String[] t, int from, int to){
		if(from <= to){
			//int taille = to - from;
			if(this.gauche != null){
				int size = this.gauche.size();
				t[from + size] = this.racine;
				this.gauche.remplir(t, from, from + size-1);
				if(this.droite != null){
					this.droite.remplir(t, from + size+1, to);
				}
			}else{
				t[from] = this.racine;
				if(this.droite != null){
					this.droite.remplir(t, from + 1, to);
				}
			}
		}
	}

	/**
	 * Test
	 * @param args
	 */
	public static void main(String[] args) {

		System.out.println("###############################");

		ABRString arbre2;
		try {

			arbre2 = new ABRString(new TextFileReader(new File("dicts/english.jsc")).readerToArray());

			String[] tableau = arbre2.tableau();

			System.out.println(arbre2.tableau().length);
			for(int i = 0; i < tableau.length; i++){
				if(tableau[i] == null){
					System.out.println("NULLLLLLLLL"+" "+i);
				}else{
					System.out.println(tableau[i]+" "+i);
				}
			}

			arbre2.ajouter("Arrrrrrrrr");
			tableau = arbre2.tableau();
			System.out.println(arbre2.tableau().length);
			for(int i = 0; i < tableau.length; i++){
				if(tableau[i] == null){
					System.out.println("NULLLLLLLLL"+" "+i);
				}else{
					System.out.println(tableau[i]+" "+i);
				}
			}
			System.out.println("###############################");
			System.out.println(arbre2);
			System.out.println("###############################");

			arbre2.ajouter("laaaaaaaaaaal");
			tableau = arbre2.tableau();
			System.out.println(arbre2.tableau().length);
			for(int i = 0; i < tableau.length; i++){
				if(tableau[i] == null){
					System.out.println("NULLLLLLLLL"+" "+i);
				}else{
					System.out.println(tableau[i]+" "+i);
				}
			}
			System.out.println("###############################");
			System.out.println(arbre2);
			System.out.println("###############################");


		} catch (IOException e) {
			System.out.println("Ce fichier n'existe pas.");
		}
	}
}



